package LeetCode;

import java.util.Stack;

import LeetCode.BinaryTreeInorderTraversal.TreeNode;

public class RecoverBSTree
{
  // pass both
  public void recoverTree(TreeNode root)
  {
    // Start typing your Java solution below
    // DO NOT write main() function
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode p = root;
    TreeNode cur = root;
    TreeNode prev = new TreeNode(Integer.MIN_VALUE);
    TreeNode large = root;
    TreeNode small = root;
    boolean findlarge = false;
    do {
      while (p != null) {
        stack.push(p);
        p = p.left;
      }
      p = stack.pop();
      cur = p;
      if (cur.val < prev.val && !findlarge) {
        large = prev;
        findlarge = true;
        small = cur;
      }
      if (cur.val < small.val && findlarge) {
        small = cur;
      }
      prev = cur;
      p = p.right;
    } while (p != null || !stack.empty());

    int tmp = large.val;
    large.val = small.val;
    small.val = tmp;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    TreeNode root = new TreeNode(2);
    root.left = new TreeNode(3);
    root.right = new TreeNode(1);

    RecoverBSTree r = new RecoverBSTree();
    r.recoverTree(root);
  }

}
